/**
 * 双向链表节点
 */
class DoublyLinkedNode<T> {
    public data: T;
    public prev: DoublyLinkedNode<T> | null = null;
    public next: DoublyLinkedNode<T> | null = null;
    
    constructor(data: T) {
        this.data = data;
    }
}

/**
 * 双向链表
 */
export class DoublyLinkedList<T> {
    private head: DoublyLinkedNode<T> | null = null;
    private tail: DoublyLinkedNode<T> | null = null;
    private size: number = 0;
    
    /**
     * 在链表尾部添加元素
     * @param data 数据
     */
    public append(data: T): void {
        const newNode = new DoublyLinkedNode(data);
        
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail!.next = newNode;
            this.tail = newNode;
        }
        
        this.size++;
    }
    
    /**
     * 在链表头部添加元素
     * @param data 数据
     */
    public prepend(data: T): void {
        const newNode = new DoublyLinkedNode(data);
        
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
        
        this.size++;
    }
    
    /**
     * 删除指定元素
     * @param data 数据
     * @returns 是否删除成功
     */
    public remove(data: T): boolean {
        let current = this.head;
        
        while (current) {
            if (current.data === data) {
                if (current.prev) {
                    current.prev.next = current.next;
                } else {
                    this.head = current.next;
                }
                
                if (current.next) {
                    current.next.prev = current.prev;
                } else {
                    this.tail = current.prev;
                }
                
                this.size--;
                return true;
            }
            current = current.next;
        }
        
        return false;
    }
    
    /**
     * 遍历链表
     * @param callback 回调函数
     */
    public forEach(callback: (data: T) => void): void {
        let current = this.head;
        while (current) {
            callback(current.data);
            current = current.next;
        }
    }
    
    /**
     * 获取链表大小
     */
    public getSize(): number {
        return this.size;
    }
    
    /**
     * 检查链表是否为空
     */
    public isEmpty(): boolean {
        return this.size === 0;
    }
    
    /**
     * 清空链表
     */
    public clear(): void {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}